from 树.二叉树.BuildTree import *


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.ans = 0

        def dfs(node: TreeNode):
            if not node: return []
            left = dfs(node.left)
            right = dfs(node.right)

            ans = []
            for l in left:
                ans.append(l + node.val)
                if l + node.val == targetSum:
                    self.ans += 1

            for r in right:
                ans.append(r + node.val)
                if r + node.val == targetSum:
                    self.ans += 1
            ans.append(node.val)
            if node.val == targetSum:
                self.ans += 1
            return ans

        dfs(root)
        return self.ans


if __name__ == '__main__':
    s = Solution()
    null = None
    root = build_tree_from_level_order([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1])
    r = s.pathSum(root, 22)
    print(r)
